#include <iostream>
#include "btree.h"
#include "bplustree.h"
#include "../plural/plural.h"

using namespace std;

typedef std::vector<int> doclist;

int test1()
{
	cout<<"in btreetest test1"<<endl;

	//doclist tmpdoclist;
	//int* tmpdoclist=NULL;
	//int tmpdoclist=0;

	typedef	struct jieningBtreeKVpair<int, int> insertkvp;

	insertkvp* tmpkvp = NULL;
	tmpkvp = new insertkvp(2);
	jieningBtree<int, int> theBtreeRoot(4);

	theBtreeRoot.addKvp(new insertkvp(2));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(4));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(6));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(8));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(10));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(1));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(3));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(5));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(7));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(9));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(12));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(14));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(16));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(18));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(20));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(11));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(13));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(15));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(17));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(19));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-2));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-4));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-6));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-8));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-10));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-12));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-14));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-16));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-18));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-20));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-1));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-3));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-5));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-7));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-9));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-11));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-13));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-15));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-17));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(-19));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(200));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(300));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(400));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(500));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(600));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(700));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(250));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(350));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(450));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(550));
	theBtreeRoot.doPrint();
	theBtreeRoot.addKvp(new insertkvp(650));
	theBtreeRoot.doPrint();

	char keyFindPath[512]={'\0'};

	memset(keyFindPath,'\0',512);
	insertkvp* findkeyre = theBtreeRoot.findKeyPos(914, keyFindPath);
	cout<<"findkeyre="<<(findkeyre==NULL?"none":"succ")<<", keyFindPath="<<keyFindPath<<endl;

	memset(keyFindPath,'\0',512);
	findkeyre = theBtreeRoot.findKeyPos(60, keyFindPath);
	cout<<"findkeyre="<<(findkeyre==NULL?"none":"succ")<<", keyFindPath="<<keyFindPath<<endl;

	memset(keyFindPath,'\0',512);
	findkeyre = theBtreeRoot.findKeyPos(70, keyFindPath);
	cout<<"findkeyre="<<(findkeyre==NULL?"none":"succ")<<", keyFindPath="<<keyFindPath<<endl;

	memset(keyFindPath,'\0',512);
	findkeyre = theBtreeRoot.findKeyPos(-10, keyFindPath);
	cout<<"findkeyre="<<(findkeyre==NULL?"none":"succ")<<", keyFindPath="<<keyFindPath<<endl;

	memset(keyFindPath,'\0',512);
	findkeyre = theBtreeRoot.findKeyPos(919, keyFindPath);
	cout<<"findkeyre="<<(findkeyre==NULL?"none":"succ")<<", keyFindPath="<<keyFindPath<<endl;


	memset(keyFindPath,'\0',512);
	findkeyre = theBtreeRoot.findKeyPos(717, keyFindPath);
	cout<<"findkeyre="<<(findkeyre==NULL?"none":"succ")<<", keyFindPath="<<keyFindPath<<endl;

	findkeyre = theBtreeRoot.findKeyPos(400);
	cout<<"findkeyre="<<(findkeyre==NULL?"none":"succ")<<endl;

	int keynum = theBtreeRoot.getKeyCount();
	cout<<"keynum="<<keynum<<endl;

	insertkvp* delkvp = theBtreeRoot.findToDeleteKV(650);
	cout<<"delete "<<(delkvp==NULL?"fail":"succ")<<endl;
	theBtreeRoot.doPrint();
	delkvp = theBtreeRoot.findToDeleteKV(550);
	cout<<"delete "<<(delkvp==NULL?"fail":"succ")<<endl;
	theBtreeRoot.doPrint();
	delkvp = theBtreeRoot.findToDeleteKV(450);
	cout<<"delete "<<(delkvp==NULL?"fail":"succ")<<endl;
	theBtreeRoot.doPrint();
	delkvp = theBtreeRoot.findToDeleteKV(350);
	cout<<"delete "<<(delkvp==NULL?"fail":"succ")<<endl;
	theBtreeRoot.doPrint();
	delkvp = theBtreeRoot.findToDeleteKV(250);
	cout<<"delete "<<(delkvp==NULL?"fail":"succ")<<endl;
	theBtreeRoot.doPrint();
	delkvp = theBtreeRoot.findToDeleteKV(700);
	cout<<"delete "<<(delkvp==NULL?"fail":"succ")<<endl;
	theBtreeRoot.doPrint();
	delkvp = theBtreeRoot.findToDeleteKV(600);
	cout<<"delete "<<(delkvp==NULL?"fail":"succ")<<endl;
	theBtreeRoot.doPrint();
	delkvp = theBtreeRoot.findToDeleteKV(500);
	cout<<"delete "<<(delkvp==NULL?"fail":"succ")<<endl;
	theBtreeRoot.doPrint();
	delkvp = theBtreeRoot.findToDeleteKV(400);
	cout<<"delete "<<(delkvp==NULL?"fail":"succ")<<endl;
	theBtreeRoot.doPrint();
	delkvp = theBtreeRoot.findToDeleteKV(300);
	cout<<"delete "<<(delkvp==NULL?"fail":"succ")<<endl;
	theBtreeRoot.doPrint();
	delkvp = theBtreeRoot.findToDeleteKV(200);
	cout<<"delete "<<(delkvp==NULL?"fail":"succ")<<endl;
	theBtreeRoot.doPrint();
	delkvp = theBtreeRoot.findToDeleteKV(-4);
	cout<<"delete "<<(delkvp==NULL?"fail":"succ")<<endl;
	theBtreeRoot.doPrint();
	delkvp = theBtreeRoot.findToDeleteKV(-5);
	cout<<"delete "<<(delkvp==NULL?"fail":"succ")<<endl;
	theBtreeRoot.doPrint();
	delkvp = theBtreeRoot.findToDeleteKV(-6);
	cout<<"delete "<<(delkvp==NULL?"fail":"succ")<<endl;
	theBtreeRoot.doPrint();
	delkvp = theBtreeRoot.findToDeleteKV(3);
	cout<<"delete "<<(delkvp==NULL?"fail":"succ")<<endl;
	theBtreeRoot.doPrint();
	return 0;
}

//*
int test2()
{
	typedef	struct jieningBtreeKVpair<int, int> insertkvp;

	jieningBtree<int, int> theBtreeRoot(6);
	for(int i=0;i<100;++i)
	{
		theBtreeRoot.addKvp(i);
	}

	int keynum = theBtreeRoot.getKeyCount();
	cout<<"keynum="<<keynum<<endl;

	theBtreeRoot.doPrint();
	char keyFindPath[512]={'\0'};
	insertkvp* findkeyre;

	memset(keyFindPath,'\0',512);
	findkeyre = theBtreeRoot.findKeyPos(17, keyFindPath);
	cout<<"findkeyre="<<findkeyre<<", keyFindPath="<<keyFindPath<<endl;

	memset(keyFindPath,'\0',512);
	findkeyre = theBtreeRoot.findKeyPos(40, keyFindPath);
	cout<<"findkeyre="<<findkeyre<<", keyFindPath="<<keyFindPath<<endl;

	return 0;
}

int test3()
{
	//int tmpdoclist = 0;
	typedef	struct jieningBtreeKVpair<double, int> insertkvp;
	jieningBtree<double, int> theBtreeRoot(6);
	for(int i=0;i<100;++i)
	{
		theBtreeRoot.addKvp(double(i+0.5));
	}

	int keynum = theBtreeRoot.getKeyCount();
	cout<<"keynum="<<keynum<<endl;

	theBtreeRoot.doPrint();
	char keyFindPath[512]={'\0'};
	insertkvp* findkeyre;

	memset(keyFindPath,'\0',512);
	findkeyre = theBtreeRoot.findKeyPos(17.5, keyFindPath);
	cout<<"findkeyre="<<findkeyre<<", keyFindPath="<<keyFindPath<<endl;

	memset(keyFindPath,'\0',512);
	findkeyre = theBtreeRoot.findKeyPos(40.5, keyFindPath);
	cout<<"findkeyre="<<findkeyre<<", keyFindPath="<<keyFindPath<<endl;

	return 0;

	return 0;
}
//*/

int test4()
{
	int insertkeys[256] = {
			2,4,6,8,10,12,14,16,18,20,
			1,3,5,7,9,11,13,15,17,19,
			-2,-4,-6,-8,-10,-12,-14,-16,-18,-20,
			-1,-3,-5,-7,-9,-11,-13,-15,-17,-19,
			0,100,200,300,400,500,600,700,800,900,
			50,150,250,350,450,550,650,750,850,950,
	};

	typedef	struct jieningBtreeKVpair<int, int> insertkvp;

	//insertkvp* tmpkvp = NULL;
	jieningBtree<int, int> theBtreeRoot(4);

	for(int loop=0; loop<60;++loop)
	{
		cout<<"add key["<<loop<<"] = "<<insertkeys[loop]<<endl;
		if(theBtreeRoot.addKvp(new insertkvp(insertkeys[loop])))
		{
			cout<<"add key["<<loop<<"] = "<<insertkeys[loop]<<" succ"<<endl;

			theBtreeRoot.doPrint();
			bool checkre = theBtreeRoot.doTreeCheck();
			cout<<"theBtreeRoot.doTreeCheck return "<<(checkre? "true": "false")<<endl;
		}
		else
		{
			cout<<"add key["<<loop<<"] = "<<insertkeys[loop]<<" fail"<<endl;
		}
	}

	theBtreeRoot.doPrint();
	bool checkre = theBtreeRoot.doTreeCheck();
	cout<<"theBtreeRoot.doTreeCheck return "<<(checkre? "true": "false")<<endl;

	int kvnum = theBtreeRoot.getKeyCount();
	cout<<"this btree has "<<kvnum<<" kvp"<<endl;

	insertkvp* minp = theBtreeRoot.findMinKvp();
	int minkey = minp->thekey;
	cout<<"this btree has min key "<< minkey <<endl;

	insertkvp* maxp = theBtreeRoot.findMaxKvp();
	int maxkey = maxp->thekey;
	cout<<"this btree has max key "<< maxkey <<endl;

	int loop = (maxkey+minkey)/2;
	while(true)
	{
		if(loop>maxkey || loop<minkey)
		{
			break;
		}
		cout<<"find to delete "<<loop<<endl;
		insertkvp* deleteptr = theBtreeRoot.findToDeleteKV(loop);
		if(NULL == deleteptr)
		{
			cout<<"fail to find to delete "<<loop<<endl;
		}
		else
		{
			cout<<"succ to find to delete "<<loop<<endl;
			theBtreeRoot.doPrint();
			bool checkre = theBtreeRoot.doTreeCheck();
			cout<<"theBtreeRoot.doTreeCheck return "<<(checkre? "true": "false")<<endl;
		}
		++loop;
	}

	checkre = theBtreeRoot.doTreeCheck();
	cout<<"theBtreeRoot.doTreeCheck return "<<(checkre? "true": "false")<<endl;

	loop = (maxkey+minkey)/2;
	while(true)
	{
		if(loop>maxkey || loop<minkey)
		{
			break;
		}
		cout<<"find to delete "<<loop<<endl;
		insertkvp* deleteptr = theBtreeRoot.findToDeleteKV(loop);
		if(NULL == deleteptr)
		{
			cout<<"fail to find to delete "<<loop<<endl;
		}
		else
		{
			cout<<"succ to find to delete "<<loop<<endl;
			theBtreeRoot.doPrint();
			bool checkre = theBtreeRoot.doTreeCheck();
			cout<<"theBtreeRoot.doTreeCheck return "<<(checkre? "true": "false")<<endl;
		}
		--loop;
	}
	return 0;
}

int test5()
{
	int insertkeys[256] = {
			2,4,6,8,10,12,14,16,18,20,
			1,3,5,7,9,11,13,15,17,19,
			-2,-4,-6,-8,-10,-12,-14,-16,-18,-20,
			-1,-3,-5,-7,-9,-11,-13,-15,-17,-19,
			0,100,200,300,400,500,600,700,800,900,
			50,150,250,350,450,550,650,750,850,950,
	};

	typedef	struct jieningBtreeKVpair<int, int> insertkvp;

	//insertkvp* tmpkvp = NULL;
	jieningBplustree<int, int> theBtreeRoot(4);

	for(int loop=0; loop<60;++loop)
	{
		cout<<"add key["<<loop<<"] = "<<insertkeys[loop]<<endl;
		if(theBtreeRoot.addKvp(new insertkvp(insertkeys[loop])))
		{
			cout<<"add key["<<loop<<"] = "<<insertkeys[loop]<<" succ"<<endl;

			//theBtreeRoot.doPrint();
			//bool checkre = theBtreeRoot.doTreeCheck();
			//cout<<"theBtreeRoot.doTreeCheck return "<<(checkre? "true": "false")<<endl;
		}
		else
		{
			cout<<"add key["<<loop<<"] = "<<insertkeys[loop]<<" fail"<<endl;
		}
	}

	//return 0;
	theBtreeRoot.doPrint();
	bool checkre = theBtreeRoot.doTreeCheck();
	cout<<"theBtreeRoot.doTreeCheck return "<<(checkre? "true": "false")<<endl;

	jieningBplustree<int, int>* minNode = NULL;
	insertkvp* tmpkvp = NULL;
	cout<<endl<<endl<<"vist all from min to max"<<endl;
	if(theBtreeRoot.findMinKvp(tmpkvp, minNode))
	{
		while(NULL != minNode)
		{
			minNode->doPrint();
			minNode = minNode->getPostLeaf();
		}
	}

	cout<<endl<<endl<<"vist all from max to min"<<endl;
	if(theBtreeRoot.findMaxKvp(tmpkvp, minNode))
	{
		while(NULL != minNode)
		{
			minNode->doPrint();
			minNode = minNode->getPreLeaf();
		}
	}
	return 0;
}

int test6()
{
	long insertkeys[256] = {
			2,4,6,8,10,12,14,16,18,20,
			1,3,5,7,9,11,13,15,17,19,
			-2,-4,-6,-8,-10,-12,-14,-16,-18,-20,
			-1,-3,-5,-7,-9,-11,-13,-15,-17,-19,
			0,100,200,300,400,500,600,700,800,900,
			50,150,250,350,450,550,650,750,850,950,
	};

	typedef	struct jieningBtreeKVpair<long, long> insertkvp;

	//insertkvp* tmpkvp = NULL;
	jieningBplustree<long, long> theBtreeRoot(4);

	for(int loop=0; loop<60;++loop)
	{
		cout<<"add key["<<loop<<"] = "<<insertkeys[loop]<<endl;
		if(theBtreeRoot.addKvp(new insertkvp(insertkeys[loop])))
		{
			cout<<"add key["<<loop<<"] = "<<insertkeys[loop]<<" succ"<<endl;

			//theBtreeRoot.doPrint();
			//bool checkre = theBtreeRoot.doTreeCheck();
			//cout<<"theBtreeRoot.doTreeCheck return "<<(checkre? "true": "false")<<endl;
		}
		else
		{
			cout<<"add key["<<loop<<"] = "<<insertkeys[loop]<<" fail"<<endl;
		}
	}

	//return 0;
	theBtreeRoot.doPrint();
	
	jieningBplustree<long, long>* minNode = NULL;
	insertkvp* tmpkvp = NULL;
	theBtreeRoot.findMinKvp(tmpkvp, minNode);
	long minkey = NULL == tmpkvp ? 0 : tmpkvp->thekey;
	minkey -= 10;
	
	theBtreeRoot.findMaxKvp(tmpkvp, minNode);
	long maxkey = NULL == tmpkvp ? 0 : tmpkvp->thekey;
	maxkey += 10;

	char findPath[1024]={'\0'};
	struct jieningBtreeKVpair<long, long>* tmpKvp=NULL;
	jieningBplustree<long, long>* targetNode = NULL;
	for(int loop = minkey; loop<= maxkey;++loop)
	{
		break;
		memset(findPath, '\0', 1024);
		//bool searchKeyPos(const BTRKT& keyval, struct jieningBtreeKVpair<BTRKT, BTRVT>*& targetKvp, jieningBplustree*& targetNode, char* pathinf=NULL);
		if(theBtreeRoot.searchKeyPos(loop, tmpKvp, targetNode, findPath))
		{
			cout<<"succ to find key "<<loop<<", findpath="<<findPath<<endl;
		}
		else
		{
			cout<<"fail to find key "<<loop<<", findpath="<<findPath<<endl;
		}
	}
	
	for(int loop = minkey; loop<= maxkey;++loop)
	{
		memset(findPath, '\0', 1024);
		//bool searchKeyPos(const BTRKT& keyval, struct jieningBtreeKVpair<BTRKT, BTRVT>*& targetKvp, jieningBplustree*& targetNode, char* pathinf=NULL);
		if(theBtreeRoot.searchToDeleteKV(loop, tmpKvp, findPath))
		{
			cout<<"succ to find to del key "<<loop<<endl;
			theBtreeRoot.doPrint();
			bool checkre = theBtreeRoot.doTreeCheck();
			cout<<"theBtreeRoot.doTreeCheck return "<<(checkre? "true": "false")<<endl;
		}
		else
		{
			cout<<"fail to find to del key "<<loop<<endl;
		}
	}

	return 0;
}

int test7()
{
	return 0;
}

int main()
{
	//test1();
	//test2();
	//test3();
	//test4();
	//test5();
	test6();
	test7();
	return 0;
}
